Packet switched communication networks are commonly employed to transfer data between communication terminals over a shared communication channel, such as a coaxial cable, fiber-optic cable, or radio channel. Such communication networks are used to transmit digital data among computers and to link office equipment such as word processors, printers, document scanners, and telefax equipment in a business office environment.
The tradeoffs in providing such a communication network are efficiency, transmission delay, economy, and reliability. Since the communication channel itself is generally a scarce resource, the network must operate to achieve maximum effective use of the channel. To achieve reliability, the system must be designed so that a failure in one part of the system does not lead to an overall shut-down of the communication network.
One type of data communication network that has been found to satisfy many of these needs is the CSMA/CD (carrier sense multiple access with conflict detection). A successful commercial embodiment of CSMA/CD is ETHERNET developed by Xerox Corporation (see U.S. Pat. No. 4,063,220 issued Dec. 13, 1977 to Metcalfe et al).
In a CSMA/CD network, the communication channel is shared by a plurality of terminals. In this type of broadcast multiple-access network, no central device is employed to control the access to the channel. A terminal transmits data packets to other terminals via the common channel, and decisions regarding the transmissions are made according to each terminal's independent observations of the traffic on the channel. Each data packet contains the address of the intended receiver, and is received by all the terminals on the network. Since no central control device is employed, there is less chance that a failure can disable the entire system, thus maximizing the reliability of the system. In CSMA/CD systems, a terminal that is ready to send a packet over the channel, first listens to the channel (carrier sensing) to determine if any other terminal is transmitting. If the channel is busy, the ready terminal waits until it senses that the channel is idle. When the channel is idle (no carrier sensed) the terminal starts transmitting a packet. It is possible in the CSMA/CD system that two or more terminals will transmit simultaneously. This results in a collision. Each terminal has the capability of detecting a conflict resulting from such a collision (conflict detection). When a conflict is detected, all the terminals stop transmitting, and execute a routine to resolve the conflicts. In the ETHERNET system, this routine comprises each terminal delaying for a random period of time before attempting to retransmit.
While data communication systems such as ETHERNET have proliferated, the need has arisen for transmitting not only conventional data packets which are all of the same length, but also various packets of different lengths.
One example of the need for this type of integrated communication is the need to transmit high quality image information along with conventional data messages over a common data communications network. Specific instances of such a need include the transmission of patient data and X-ray images over a local network within a hospital, or between hospitals or clinics; and the transmission of text and high quality photographic images in an electronic printing environment. Another example is the communication of voice information and conventional data over a communication network, where limited delays of the voice packets are tolerated. In such integrated communication networks, the channel traffic would consist of relatively short packets, and relatively longer packets (e.g. one or more orders of magnitude longer). Data packets are generally 10 to 100 times longer than voice packets, and similarly image packets are generally 10 to 100 times longer than data packets. An entire image is generally three or four orders of magnitude larger than a single data packet, but the single image may be partitioned into 100 or more image packets, so that the image packet is only one to two orders of magnitude larger than a data packet.
It is a straight forward design task to provide a separate channel capable of handling each of the packet sizes to be transmitted. However such a multichannel system is quite expensive. It would be desirable therefore if a single channel network could be adapted to handle efficiently mixed packet sizes.
The problem with this approach is that although the known CSMA/CD systems provide fast access and efficient use of the channel in a local environment, the systems suffer from instability. That is when heavy traffic is applied to the system for a short time such that the system capacity is momentarily exceeded, the system will lock up into a saturated state from which it cannot recover. In this state, the total channel capacity is consumed by attempts to resolve the conflicts and no successful transmissions can take place. Because image packets, for example, would behave as extremely heavy traffic, the problem of instability is encountered in an integrated data/image network.
A packet switched data communication system incorporating a technique called a random splitting or tree method has been proposed. The random splitting or tree method has been mathematically proven to be stable in the presence of bursts of heavy traffic. See the article "Tree Algorithms for Packet Broadcast Channels" by John 1. Capetanakis, IEEE TRANSACTIONS ON INFORMATION THEORY, Vol. IT-25 No. 5, Sept. 1979.
The basic random splitting or tree method was designed for a slotted channel. The length of each slot is equal to the length of a data packet. It requires that each active user of the channel determine his transmission or retransmission according to his independent observations of the global results of the past channel transmissions which are referred to as channel feedbacks. The inherent feedback is ternary, i.e. any user can distinquish the past transmission to be either empty, successful, or in conflict. Users make decisions at slot boundaries. In this method, the communication system alternates between two modes, normal mode and conflict resolution mode. When a collision occurs in normal mode, all transmitters go into conflict resolution mode, all new arrivals wait until the next transition into normal mode, and all packets involved in the collision independently select one of two subsets with equal probability. Each subset can be viewed as corresponding to a branch from the root of a rooted binary tree. In the slot following the collision, the first of these subsets is transmitted. If another collision occurs, this subset is further split into two smaller subsets, corresponding to further branches growing from the original branch. The first of these subsets is transmitted in the next slot, and if this transmission is successful or idle, the second of the subsets is transmitted in the following slot. In general, whenever the transmission of a subset results in a collision, the subset is split and two new branches of the tree are grown from the old branch. Whenever the transmission of a subset is idle or successful (i.e. the slot is empty or contains one packet), the next slot is used to transmit the next subset. When all subsets have been exhausted, the normal mode is again entered.
In theory, the random splitting or tree method has been shown to be absolutely stable. It is capable of achieving a maximum throughput rate of 0.347 packets/slot. However, when it is applied to a local area network, this rate seems too low. Furthermore, it has not been shown how the random splitting or tree method could be implemented distributively in a communication network.
It is therefore the object of the present invention to provide a stable distributively controlled communication system that implements the random splitting or tree method with improved channel throughput. It is a further object of the present invention to provide an integrated data/image network that implements the random splitting or tree method.